/**
 * skiplist.h
 * 类型及接口原型声明。*/

#ifndef SKIPLIST_H
#define SKIPLIST_H

#include "comm.h"

typedef struct sklList SKL_S;
typedef struct sklNode SKL_NODE_S;

/**
 * 跳表状态码。
 * OK 正常；
 * OM 无内存；
 * NK 失败；*/
typedef enum sklStatus
{
    SKL_OK = 0,
    SKL_OH,
    SKL_OM,
} SKL_STATUS_E;

/** 
 * 值比较函数类型：
 * 参数，usr 用户数据，d 跳表结点数据；
 * 返回值，d > usr 返大于 0 的数；
 *        d < usr 返小于 0 的数；
 *        d == usr，返 0 。
 * 该函数交于使用跳表者实现。*/
typedef int (*SKL_VCMPF)(const COMM_DATA_U *d, const void *usr);

/**
 * 值设置和去设置函数类型：
 * 参数，usr 用户数据，d 跳表结点数据；
 * 返回值，成功 SKL_OK；其他见错误码。*/
typedef int (*SKL_VSETF) (COMM_DATA_U *d, const void *usr);
typedef int (*SKL_VRSETF)(COMM_DATA_U *d, const void *usr);

/**
 * 默认值设置函数。
 * 
 * 若可忽略 COMM_DATA_U 按最大长度进行赋值的性能影响，不妨用此函
 * 数作为值设置函数。*/
inline static int sklValSet(COMM_DATA_U *d, const void *usr)
{
    *d = * (COMM_DATA_U *)usr;
    return SKL_OK;
}

/**
 * 默认值去设置函数。
 * 
 * uext 为调用者特定数据，用于对 d 的去设置，
 * 如将跳表释放的 d 挂在于 uext 中。*/
inline static int sklValRset(COMM_DATA_U *d, const void *uext)
{
    (void)d, (void)uext;
    return 0;
}

/**
 * 外部参数任命(appoint)类型：
 * malloc 内存分配函数；
 * mfree  内存释放函数；
 * —— 欢迎更好的虚址管理函数，暂无赋 NULL。
 * uext   用户扩展，无则赋 NULL；
 * vrset  去赋值回调，无则赋 NULL；
 * vset   赋值回调，无则赋 NULL；
 * vcmp   值比较回调；
 * adjthr 调整补偿阀值；
 * adjust 是否对跳表模型进行调整补偿；
 * step   1/step 为跳表结点增长概率
 * lvm    跳表最大层数限制。
 * 
 * 注：在实现跳表层级增长时，随跳表容纳量增加，
 * 伪随机数可能模拟不了理想跳表模型，当 adj 不
 * 为 0 时内部会为此作一些补偿尝试。对于 C 伪随
 * 机函数 rand_r()，阀值 thr 取 1MiB ~2MiB 时，
 * 当数据量上升到几十兆/百兆/GiB时搜索性能可提升
 * 1~2或2~3倍。
 * 
 * 此处将该参数提供出来以供实际场景调整取最佳值。*/
typedef struct sklApp
{
    void *(*malloc)(size_t);
    void  (*mfree )(void *);
    void *uext;
    SKL_VRSETF vrset;
    SKL_VSETF  vset;
    SKL_VCMPF  vcmp;
    uint64_t adjthr;
    int step,lvm;
    int adjust;
} SKL_APP_S;

/**
 * 根据任命参数 app 创建跳表。*/
SKL_S * sklAppoint(const SKL_APP_S *app);

/**
 * 释放跳表 skl 相关资源。
 * 注：若 skl->app.vrset 潜在会失败，
 * 则可先通过 sklFind/sklDel 迭代删
 * 除容纳于跳表中的数据。*/
void sklRemove(SKL_S *skl);

/**
 * 往跳表 skl 中根据 skl->app.vset 插入值 usr。
 * 返回值：usr 插入成功后值地址；失败，NULL。*/
const COMM_DATA_U * sklPut(SKL_S *skl, const void *usr);

/**
 * 在跳表 skl 中根据 skl->app.vcmp 获取 usr 指定值；
 * 该函数返回指定值地址（存在）或恰大于 usr 值的地址
 *（usr 对应值不存在且存在大于 usr 的值）；否则返 NULL。*/
const COMM_DATA_U * sklGet(const SKL_S *skl, const void *usr);

/**
 * 在跳表 skl 中根据 skl->app.vcmp 删除 usr 指定值。
 * 
 * 返回值，删除成功则返回删除值下一个值地址，失败或下一个值
 * 不存在则返 NULL。
 * 注：usr 对应值的清理工作需在 skl->app.vrset 中完成。*/
const COMM_DATA_U * sklDel(SKL_S *skl, const void *usr);

/**
 * 跳转到跳表 skl 最后一个值处并返回其地址，若
 * 跳表为空则返 NULL。*/
const COMM_DATA_U * sklSeekLast(SKL_S *skl);

/**
 * 跳转到跳表 skl 第一个值处并返回其地址，若跳表
 * 为空则返 NULL。*/
const COMM_DATA_U * sklSeekFirst(SKL_S *skl);

/**
 * 跳转到 usr 指定值处（若存在）或恰大于 usr 值处并返回其地址，
 * 失败返 NULL。*/
const COMM_DATA_U * sklSeek(SKL_S *skl, const void *usr);

/**
 * 返回跳表 skl 当前位置值地址，并向前迭代。*/
const COMM_DATA_U * sklPrev(SKL_S *skl);

/**
 * 返回跳表 skl 当前位置值地址，并向后迭代。*/
const COMM_DATA_U * sklNext(SKL_S *skl);

#endif